package com.huangyi;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 摆动序列
    static class Solution {
        public int wiggleMaxLength(int[] nums) {
            int n = nums.length;
            if (n <= 1) return n;

            int[] f = new int[n]; // 以正差结尾
            int[] g = new int[n]; // 以负差结尾
            Arrays.fill(f, 1);
            Arrays.fill(g, 1);

            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        f[i] = Math.max(f[i], g[j] + 1);
                    } else if (nums[i] < nums[j]) {
                        g[i] = Math.max(g[i], f[j] + 1);
                    }
                    // 相等不更新
                }
            }

            int ans = 1;
            for (int i = 0; i < n; i++) {
                ans = Math.max(ans, Math.max(f[i], g[i]));
            }
            return ans;
        }
    }
}